//
// Created by 梦小星 on 2021/10/24.
// @author 梦小星 https://mengxiaoxing.top
// @mail mengxingcn@aliyun.com
//
#include <iostream>
#include "SqList.h"
/*
 * 删除有序表中所有值重复的元素
 * 算法思想 因为表为顺序表，使用双指针i ，j分别指向当前元素和后一个元素时即可检查相邻两个元素是否重复，
 * 若重复则将k的值加一，记录重复的元素个数，也即后续遇到不同元素时，不同元素向前移动的位数
 * 如果不重复则将i指向的元素前移k个位置，即前移到i-k个位置
 * */
void deDuplication(SqList &list) {
//    设置k记录重复的元素的个数，
    int k =0 ;
//    指针ij一前一后分别指向相邻的元素，同时往后扫描
    for (int i = 0, j = 1; j < list.length; ++i,++j) {
        if (list.data[i]==list.data[j]){
            k++;
        } else{
//            如果遇到不同的元素则向前移动
            list.data[i-k]=list.data[i];
        }
    }
    list.length-=k;
}
// 方法二
bool delete_Same(SqList &list) {
    if (list.length == 0 || list.length == 1) {//长度为0或者1的时候 无重复元素
        return false;
    }
    int i, j;//i用于记录上一个不一样的元素的下标， j用于循环遍历 从数组的第二个元素（下标为1开始）
    for (i = 0, j = 1; j < list.length; ++j) {
        if (list.data[i] != list.data[j]) {
            list.data[++i] = list.data[j];//原理同3
        }

    }
    list.length = i + 1;//调整表长度 表长度至少为1个因为第一个元素肯定不同
    return true;
}
int main() {
    SqList list;
    initList(list);
    int data[] = {3,  3, 5, 6,6,6, 8, 9,9,10 };

    int dataSize = sizeof(data) / sizeof(int);
    for (int i = 0; i < dataSize; ++i) {
        list.data[i] = data[i];
    }
    list.length = dataSize+1;
    for (int i = 0; i < list.length; ++i) {
        std::cout << list.data[i] << ",";
    }
    std::cout << std::endl;
    deDuplication(list);
    for (int i = 0; i < list.length; ++i) {
        std::cout << list.data[i] << ",";
    }
}